/**
 * @a https://leetcode.cn/problems/sort-an-array/description/
 */

#include "common.h"
class Solution
{
public:
    vector<int> sortArray(vector<int> &nums)
    {
        qSort(nums.begin(), nums.end());
        return nums;
    }

    void qSort(vector<int>::iterator first, vector<int>::iterator last)
    {
        if (first >= last)
            return; // 终止条件：空或单元素区间

        // 三数取中法选择 pivot
        auto mid = first + std::distance(first, last) / 2;
        int x1 = *first, x2 = *std::prev(last), x3 = *mid;
        int pivot = std::max(std::min(x1, x2), std::min(std::max(x1, x2), x3));

        // 三路划分
        auto left = first, right = last - 1, cur = first;
        while (cur <= right)
        {
            if (*cur < pivot)
            {
                std::iter_swap(cur++, left++);
            }
            else if (*cur > pivot)
            {
                std::iter_swap(cur, right--);
            }
            else
            {
                cur++;
            }
        }

        // 递归排序左右部分
        qSort(first, left);
        qSort(right + 1, last);
    }
};

// 这种写法不好  qSort 可以传递迭代器,而且我每次递归都会拷贝
// class Solution
// {
// public:
//     vector<int> sortArray(vector<int> &nums)
//     {
//         qSort(nums);
//         return nums;
//     }
//     void qSort(vector<int> part)
//     {
//         int sz = part.size();
//         if (sz == 1)
//             return;
//         int left = 0, right = sz - 1;
//         int x1 = part[left], x2 = part[right], x3 = part[(left + right) / 2];
//         int pivot = x1 > x2 ? (x1 < x3 ? x1 : (x2 > x3 ? x2 : x3))
//                             : (x2 < x3 ? x2 : (x3 < x1 ? x1 : x3));
//         // 三数取中 还有其他两种写法
//         // int pivot = (x1 + x2 + x3) - max(x1,x2,x3) - min(x1,x2,x3);
//         // int pivot = min(max(x1,x2), max(min(x1,x2), x3));

//         for (int i = 0; i < right;)
//         {
//             if (part[i] < pivot)
//             {
//                 swap(part[i++], part[left++]);
//             }
//             else if(part[i] > pivot){
//                 swap(part[i], part[right--]);
//             }
//             else{
//                 i++;
//             }
//         }
//         // recursing
//         qSort(part,)
//     }
// };

class Solution
{
public:
    vector<int> sortArray(vector<int> &nums)
    {
        qSort(nums.begin(), nums.end());
        return nums;
    }
    void qSort(vector<int>::iterator begin, vector<int>::iterator end)
    {
        if (begin >= end - 1)
            return;
        int sz = end - begin;
        int x1 = *begin, x2 = *(end - 1), x3 = *(begin + (sz - 1) / 2);
        int pivot = min(max(x1, x2), min(max(x1, x2), x3));
        auto left = begin, right = end - 1, cur = begin;
        while (cur <= right)
        {
            if (*cur < pivot)
            {
                iter_swap(left, cur);
                ++left, ++cur;
            }
            else if (*cur > pivot)
            {
                iter_swap(right, cur);
                --right;
            }
            else
            {
                ++cur;
            }
        }
        qSort(begin, left);
        qSort(right + 1, end);
    }
};

void quick_sort(vector<int>::iterator begin, vector<int>::iterator end)
{
    if (begin >= end - 1) return;
    auto mid = begin + ((end - begin) >> 1);
    int x1 = *begin, x2 = *(end - 1), x3 = *mid;
    int pivot = max(min(x2, x3), min(max(x2, x3), x1));
    auto cur = begin, left = begin, right = end - 1;
    while (cur <= right) {
        if (*cur < pivot) {
            iter_swap(left++, cur++);
        }
        else if (*cur > pivot) {
            iter_swap(right--, cur);
        }
        else {
            ++cur;
        }
    }
    quick_sort(begin, left);
    quick_sort(right + 1, end);
}

void merge_sort(vector<int>::iterator begin, vector<int>::iterator end){
    int sz = end - begin;
    if(sz <= 1) return;
    auto mid = begin + (sz >> 1);
    
    merge_sort(begin, mid);
    merge_sort(mid, end);
    
    vector<int> tmp(sz);
    auto cur1 = begin, cur2 = mid;
    int i = 0;
    while(cur1 < mid && cur2 < end){
        if(*cur1 < *cur2){
            tmp[i++] = *cur1++;
        }
        else{
            tmp[i++] = *cur2++;
        }
    }
    while(cur1 < mid) tmp[i++] = *cur1++;
    while(cur2 < end) tmp[i++] = *cur2++;
    
    copy(tmp.begin(), tmp.begin() + sz, begin);
}


int main()
{
    auto arr = new vector<int>({ 2, 7, 3, 5, 8, 1, 6, 9 });
    quick_sort(arr->begin(), arr->end());
    for (auto iter = arr->begin(); iter < arr->end(); ++iter) {
        cout << *iter << ' ';
    }

    delete arr;
    return 0;
}